/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Jared
 * Date: 2022-12-07
 * Time: 1:20
 */
public class Demo {
    /**
     * 递归：方法自己调用自己。
     * 实现递归，需要去推导一个递归公式，递归难就难在如何快速的找到这个公式。
     * 递归的前提是：1、有一个趋近于中止的条件 2、自己调用自己
     * 思考递归的时候是横向思考，代码的执行是纵向执行
     */

    public static void func(int n){
        if(n==1){
            return;
        }
        func(n-1);
    }

    /**
     * 递归求n的阶乘 递归公式为 :n*(n-1)!
     * @param n
     * @return
     */
    public  static int fac(int n){
        if(n==1){
            return 1;
        }
        return n*fac(n-1);
    }

    /**
     * 递归求1到 n的和
     * @param n
     * @return
     */
    public static int sumAdd(int n){
        if(n==1){
            return  1;
        }
        return n+sumAdd(n-1);
    }

    /**
     * 按顺序打印数字的每一位
     * @param n
     */
    public static void print(int n){
        if(n<10){
            System.out.println(n%10+" ");
        }
        else {
            print(n/10);
            System.out.println(n%10+" ");
        }
    }

    /**
     * 递归返回一个数字的每一位之和
     * @param n
     * @return
     */
    public static int sumEveryOne(int n){
        if(n<10){
            return n;
        }
        else{
            return sumEveryOne(n/10)+n%10;
        }
    }

    /**
     * 递归 求斐波那契数列的第n项
     * @param n
     * @return
     */
    public static int fib(int n){
        if(n==1||n==2){
            return 1;
        }
        else {
            return fib(n-1)+fib(n-2);
        }
    }

    /**
     * 循环(迭代)实现斐波那契数列
     * @param n
     * @return
     */
    public static int fib2(int n){
        if(n==1||n==2){
            return 1;
        }
        int f1=1;
        int f2=1;
        int f3=0;
        for (int i = 3; i <=n; i++) {
            f3 = f1+f2;
            f1 = f2;
            f2 = f3;
        }
        return  f3;
    }

    /**
     * 递归实现 青蛙跳台阶问题
     * @param n
     * @return
     */
    public static int forgJump(int n) {
        if(n==1||n==2){
            return n;
        }
        else {
            return forgJump(n-1)+forgJump(n-2);
        }
    }

    /**
     * 循环(迭代)实现青蛙跳台阶
     * @param n
     * @return
     */
    public static int forgJump2(int n) {
        if(n==1||n==2){
            return n;
        }
        int f1=1;
        int f2=2;
        int f3=0;
        for (int i = 3; i <=n; i++) {
            f3 = f1+f2;
            f1 = f2;
            f2 = f3;
        }
        return  f3;
    }

    public static void main(String[] args) {
        System.out.println(forgJump(5));
    }
}
